A storage system usually includes a host and a storage device, such as a non-volatile memory device. The storage device typically includes a plurality of physical blocks for storing data, and upon receiving a write command from the host, writes data to one of the physical blocks that is designated for writing the data. After the data are written to the storage device, the host may send a command (trim command) to invalidate the written data, for example when new data are overwritten. As a result, data written in the storage device may include both valid and invalid data.
When a capacity of free space in the physical blocks decreases to a certain level, one type of storage device carries out garbage collection (GC) with respect to some of the physical blocks in which data are written. Garbage collection is a process of copying all valid data from target physical blocks to another physical block, and erasing the target physical blocks. By erasing the target physical blocks, the target physical blocks can be used for new data writing.
However, if the garbage collection is carried out in the storage device when the host transmits an access command (e.g., a write command and a read command) to the storage device, the access command cannot be carried out immediately, and need to be carried out after the garbage collection ends. As a result, latency of the access increases.
In one type of a storage system, the host can control the timing to perform the GC, that is, performs host-initiated garbage collection using a function of background operation control. Specifically, the host-initiated garbage collection may be performed when the host is in an idle state, that is, the host does not transmit access commands to the storage device, and not performed when the host is in a busy state, that is, the host transmits access commands to the storage device. As a result, conflict between operation of the garbage collection and access operation can be avoided.
Such garbage collection is conventionally carried out in unit of block. That is, valid data that amount to a size of one block are collected from a plurality of active blocks, and the one block is filled with the collected valid data. However, it may take several hundred milliseconds to fill the entire block with the collected valid data, and during the period to fill the block, no access from the host to the storage device can be performed. Conversely, if a period during which the host becomes the idle state is less than the several hundred milliseconds, the host-initiated garbage collection may not be performed at all.